#include <bits/stdc++.h>
using namespace std;
const int N=4000005;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int mod,Q,n,m,ans,jc[N],in[N],t[2005][2005],inv2;
#define pow Pow
int pow(int x,int base){
    int ans=1;
    while(base){
        if(base&1) ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        base>>=1;
    }
    return ans;
}
int inv(int x){
    return pow(x,mod-2);
}
int C(int n,int m){
    if(n<0||m<0||m<n) return 0;
    if(!in[m-n]) in[m-n]=inv(jc[m-n]);
    if(!in[n]) in[n]=inv(jc[n]);
    return 1ll*jc[m]*in[m-n]%mod*in[n]%mod;
}
signed main(){
    freopen("pr.in","r",stdin);
    freopen("pr.out","w",stdout);
    mod=read(),Q=read();
    inv2=inv(2);
    jc[0]=1;
    for(int i=1;i<=N-1;i++) jc[i]=1ll*jc[i-1]*i%mod;
    while(Q--){
        n=read(),m=read();
        if(t[n][m]){
            cout<<t[n][m]<<"\n";
            continue;
        }
        ans=0;
        for(int i=0;i<=(n*m-1)/2;i++){
            int sum=0;
            for(int j=0;i-j*(m+1)>=0;j++) sum=(sum+1ll*(j&1?-1:1)*C(j,n)*C(n-1,i-j*(m+1)+n-1)%mod+mod)%mod;
            ans=(ans+1ll*sum*sum%mod)%mod;
        }
        ans=ans*2%mod;
        if((n*m-1)&1){
            int i=(n*m-1)/2+1;
            int sum=0;
            for(int j=0;i-j*(m+1)>=0;j++) sum=(sum+1ll*(j&1?-1:1)*C(j,n)*C(n-1,i-j*(m+1)+n-1)%mod+mod)%mod;
            ans=(ans+1ll*sum*sum%mod)%mod;
        }
        int zs=pow(m+1,2*n);
        t[n][m]=1ll*(zs-ans+mod)%mod*inv2%mod*inv(zs)%mod;
        cout<<t[n][m]<<"\n";
    }
    return 0;
}